// https://leetcode.cn/problems/super-pow/
// Created by ade on 2022/11/10.
//
#include <iostream>
#include <vector>
#include "math.h"

using namespace std;

class Solution {
public:
    int MOD = 1337;

    /*int pow(int x, int n) {
        long res = 1;
        while (n) {
            if (n % 2 == 1) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            n /= 2;
        }
        return res;
    }

    int superPow1(int a, vector<int> &b) {
        int res = 1;
        for (int i = b.size() - 1; i >= 0; i--) {
            res = res * pow(a, b[i]) % MOD;
            a = pow(a, 10);
        }
        return res;
    }*/

    int pow(int a, int b) {
        int res = 1;
        while (b > 0) {
            if (b % 2 == 1) res *= a % MOD;
            a = (a % MOD) * (a % MOD);
            b >>= 1;
        }
        return res % MOD;
    }

    int dfs(int a, vector<int> &b, int index) {
        if (index == -1) return 1; // 初始状态是1
        return pow(dfs(a, b, index - 1), 10) * pow(a, b[index]) % MOD;
    }

    int superPow(int a, vector<int> &b) {
//        int res = 1;
//        int len = b.size();
//        for (int i = len - 1; i >= 0; i--) {
//            res = pow(a, b[i]) % MOD;
//            a = pow(a, 10) % MOD;
//        }
//        return res;
        return dfs(a, b, b.size() - 1);
    }
};

int main() {
    Solution so;
    cout << so.pow(2, 20) << endl;
    return 0;
    int a = 2;
    vector<int> b = {4, 3, 3, 8, 5, 2};
    cout << so.superPow(a, b) << endl;
    return 0;
}